package 剑指专题.二叉树;


/*
 * Author：江松
 * Date：2023/3/25 12:39
 *
 *
 法1：最容易想到
 遍历每个点，然后遍历它的左右子树比较高度，如果超过就错了
 法2：用HashMap做一个记忆化
 法1：
 自底向上，因为求高度是后序操作，边求高度边比较
 */

public class Main10 {
    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }
    }

    public int checkDepth(TreeNode root){
        if(root==null)return 0;
        int l=checkDepth(root.left);
        int r=checkDepth(root.right);
        return Math.abs(r-l)<=1?Math.abs(r-l):-1;
    }
    public boolean IsBalanced_Solution(TreeNode root) {
        return checkDepth(root)!=-1;
    }
    /*
    public int getDepth(TreeNode root){
        if(root==null)return 0;
        return Math.max(getDepth(root.left),getDepth(root.right))+1;
    }

    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null)return true;
        int l=getDepth(root.left);
        int r=getDepth(root.right);
        return Math.abs(r-l)<1&&IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
    }
    */
}
